package avltree;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 苏李涛
 * Date: 2024-08-18
 * Time: 18:00
 */

public class AVLTree {
    static class TreeNode{
        public int val;
        public int bf;//平衡因子
        public TreeNode left;
        public TreeNode right;
        public TreeNode parent;//父亲节点的引用

        public TreeNode(int val) {
            this.val = val;
        }

    }
    public TreeNode root;

    //插入：
    public boolean insert(int val) {
        TreeNode node = new TreeNode(val);

        if(root == null){
           root = node;
           return true;
        }

        TreeNode cur = root;
        TreeNode parent = null;
        while (cur != null){
            if(cur.val < val){
                parent = cur;
                cur = cur.right;
            }else if(cur.val > val){
                parent = cur;
                cur = cur.left;
            }else {
                return false;
            }
        }

        if(parent.val < val){
            parent.right = node;
        }else{
            parent.left = node;
        }




        node.parent = parent;
        cur = node;//指向新插入的节点

        //修改平衡因子
        while (parent != null) {
            //先看cur在parent的左边还是右边
            if (cur == parent.right) {
                //如果在右边就++
                parent.bf++;
            } else {
                //如果在左边就--
                parent.bf--;
            }

            //检查当前的平衡因子是不是0，1，-1
            if (parent.bf == 0) {
                //已经平衡了
                break;

            } else if (parent.bf == 1 || parent.bf == -1) {
                //继续向上修改平衡因子
                cur = parent;
                parent = cur.parent;

            } else {
                if(parent.bf == 2){//右树高-》降低右數高度
                    if(cur.bf == 1){
                        //左单旋
                        rotateLeft(parent);
                    }else {
                        //cur.bf == -1
                        //右左双旋：
                        rotateRL(parent);

                    }
                }else {
                    //parent.bf == -2//左树高-》降低左树高度
                    if(cur.bf == -1){
                        //右单旋
                        rotateRight(parent);
                    }else {
                        //cur.bf == 1
                        //左右双旋：
                        rotateLR(parent);
                    }
                }
                //已经平衡
                break;
            }
        }
        return true;
    }


    /**
     *右左双旋：
     * @param parent
     */
    private void rotateRL(TreeNode parent) {
        TreeNode subR = parent.right;
        TreeNode subRL = subR.left;
        int bf = subRL.bf;

        rotateRight(parent.right);
        rotateLeft(parent);


        //双旋时subRL的值-1,1，会有2种插入方式
        if(bf == 1){
            parent.bf = -1;
            subRL.bf = 0;
            subR.bf = 0;
        }else if(bf == -1){
            parent.bf = 0;
            subRL.bf = 0;
            subR.bf = 1;
        }
    }


    /**
     *左右双旋：
     * @param parent
     */
    private void rotateLR(TreeNode parent) {
        TreeNode subL = parent.left;
        TreeNode subLR = subL.right;
        int bf = subLR.bf;

        rotateLeft(parent.left);
        rotateRight(parent);


        //双旋时subLR的值-1,1，会有2种插入方式
        if(bf == -1){
            subL.bf = 0;
            subLR.bf = 0;
            parent.bf = 1;
        }else if(bf == 1){
            subL.bf = -1;
            subLR.bf = 0;
            parent.bf = 0;
        }
    }


    /**
     * 右单旋
     * @param parent
     */
    private void rotateRight(TreeNode parent){
        TreeNode subL = parent.left;
        TreeNode subRL = subL.right;

        parent.left = subRL;
        subL.right = parent;
        //如果旋转的整棵树也是一个子树，记录下原来该树的父亲，后续修改
        TreeNode pParent = parent.parent;

        if (subRL != null) {
            subRL.parent = parent;
        }
        parent.parent = subL;

        //看看整棵树是否也是一个子树
        if(parent == root){
            root = subL;
            root.parent = null;
        }else {
            //是子树就确定这棵树是左子树还是右子树
            if(pParent.left == parent){
                pParent.left = subL;
            }else {
                pParent.right = subL;
            }
        }

        subL.parent = pParent;

        //修改平衡因子
        subL.bf = 0;
        parent.bf = 0;
    }


    /**
     * 左单旋
     * @param parent
     */
    private void rotateLeft(TreeNode parent) {
        TreeNode subR = parent.right;
        TreeNode subRL = subR.left;

        parent.right = subRL;
        subR.left = parent;
        TreeNode pParent = parent.parent;

        if(subRL != null){
            subRL.parent = parent;
        }
        parent.parent = subR;

        //看看整棵树是否也是一个子树
        if(parent == root){
            root = subR;
            root.parent = null;
        }else {
            //是子树就确定这棵树是左子树还是右子树
            if(pParent.left == parent){
                pParent.left = subR;
            }else {
                pParent.right = subR;
            }
        }
        subR.parent = pParent;

        parent.bf = 0;
        subR.bf = 0;
    }


    /**
     *验证是否为AVL树:
     *
     */

    //中序遍历：
    public void inorder(TreeNode root){
        if(root == null){
            return;
        }

        inorder(root.left);
        System.out.println(root.val);
        inorder(root.right);
    }

    //求高度
    private int height(TreeNode root){
        if(root == null){
            return 0;
        }

        int leftH = height(root.left);
        int rightH = height(root.right);

        return Math.max(leftH,rightH) + 1;
    }

    //判断树是否为平衡二叉树
    public boolean isBalanced(TreeNode root){
        if (root == null) return true;


        int leftH = height(root.left);
        int rightH = height(root.right);

        /**检查这棵树平衡因子是否本身就出错
         * 因为要验证的这棵树的平衡因子，是我们自己定义的，防止出错。
         */

        if(rightH-leftH != root.bf){
            System.out.println("这个节点" + root.val+ "平衡因子异常");
            return false;
        }

        return Math.abs(leftH-rightH) < 2
                && isBalanced(root.left)
                && isBalanced(root.right);
    }
}
